package com.ztom.daily.n2022.m3;


/**
 * 阶乘后的零
 * <p>
 * https://leetcode-cn.com/problems/factorial-trailing-zeroes/
 *
 * @author ZhangTao
 */
public class Day25TrailingZeroes {

    public int trailingZeroes1(int n) {
        if (n <= 0) {
            return 0;
        }

        int res = 0;
        // 2 * 5 才会产生 0, 寻找 5 的个数即可
        for (int i = 5; i <= n; i += 5) {
            int x = i;
            while (x % 5 == 0) {
                res++;
                x /= 5;
            }
        }
        return res;
    }

    /**
     * 实际上就是计算1-n之中有多少个5的因数。以130为例：
     * 第一次除以5时得到26，表明存在26个包含 [一] 个因数5的数；
     * 第二次除以5得到5，表明存在5个包含 [二] 个因数5的数(这些数字的一个因数5已经在第一次运算的时候统计了)；
     * 第三次除以5得到1，表明存在1个包含 [三] 个因数5的数(这些数字的两个因数5已经在前两次运算的时候统计了)；
     * 得到从1-n中所有5的因数的个数
     *
     * @param n
     * @return
     */
    public int trailingZeroes(int n) {
        if (n <= 0) {
            return 0;
        }

        int res = 0;
        while (n != 0) {
            n /= 5;
            res += n;
        }
        return res;
    }
}
